class Solution {
public:
    bool check(int x, vector<int>& a, int m) {
        int cnt = 0;
        int target = a[0] + x;
        for(int i = 0; i < a.size() - 1; i++) {
            if(a[i] < target && a[i + 1] >= target) {
                cnt++;
                target = a[i + 1] + x;
            }
        }
        return cnt >= m - 1;
    }
    
    int maxDistance(vector<int>& a, int m) {
        sort(a.begin(), a.end());
        int len = a.size();
        int diff = a[len - 1] - a[0];	 
        int mn = INT_MAX;	
        for(int i = 0; i < len - 1; i++) {
            if(mn > a[i + 1] - a[i]) {
                mn = a[i + 1] - a[i];
            }
        }
        if(m == 2) {	
            return diff;
        } else {
            int l = mn, r = diff / (m - 1);	
            while(l <= r) {	
                int mid = (l + r) / 2;
                if(check(mid, a, m)) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
            return l - 1;
        }
    }
};

